#include "GraphDatabase.hpp"
#include "GraphFunctions.hpp"
#include <limits.h>
#include <fstream>

#include <boost/serialization/list.hpp>
#include <boost/serialization/vector.hpp>
#include <boost/serialization/map.hpp>
#include <boost/serialization/set.hpp>

#include <boost/archive/binary_oarchive.hpp>
#include <boost/archive/binary_iarchive.hpp>

#include <boost/graph/adj_list_serialize.hpp>
#include <boost/graph/johnson_all_pairs_shortest.hpp>

#include <boost/graph/connected_components.hpp>
#include <boost/foreach.hpp>

#include <queue>
#include <boost/graph/subgraph.hpp>

using namespace std;
using namespace boost;
using namespace TopologicalLearner;

int GraphDatabase::LoadAllGraphs(std::string sDir, int iLimit, bool bUnique)
{
    m_bUnique = bUnique;
    return m_kLoader.LoadAllGraphs(sDir, m_Graphs, iLimit, bUnique);
}
//----------------------------------------------------------------
const std::vector<Graph>& GraphDatabase::GetGraphVector() const
{
    return m_Graphs;
}
//----------------------------------------------------------------
unsigned int GraphDatabase::GetVertexIDFromString(std::string sName) const
{
    std::map<std::string, int>::const_iterator it = m_kLoader.m_TypesID.find(sName);
        //string stmp = (*it);
    if( it != m_kLoader.m_TypesID.end() )
        return (*it).second;
    else return UINT_MAX;
}
//----------------------------------------------------------------
template<class Archive>
void GraphDatabase::serialize(Archive &ar, const unsigned int version)
{
    ar & m_Graphs;

    ar & m_bUnique;

    ar & m_degreeDist;

    ar & m_catgDist;

    //ar & clusters;
    //ar & m_pAllclusters;
    ar & m_FrequentSGs;

    ar & m_kLoader.m_IDTypes;
    ar & m_kLoader.m_TypesID;
    ar & m_kLoader.m_Types;
    ar & m_kLoader.m_GraphFilenames;

}
//----------------------------------------------------------------
void GraphDatabase::Save(string sFilename)
{
    ofstream ofs(sFilename.c_str(), ios::binary);

    boost::archive::binary_oarchive oa(ofs);
    oa << (*this);
    ofs.close();
}
//----------------------------------------------------------------
void GraphDatabase::Load(string sFilename)
{
    std::ifstream ifs(sFilename.c_str(), ios::binary);


    boost::archive::binary_iarchive oa(ifs);
    oa >> (*this);

    ifs.close();
}
//----------------------------------------------------------------
std::string GraphDatabase::GetStringFromVertexID(unsigned int iID) const
{
    map<int, string>::const_iterator it;
    it = m_kLoader.m_IDTypes.find(iID);
    return it->second;
}
//----------------------------------------------------------------
void GraphDatabase::GenerateFrequentSubgraphs(double dFreq)
{
    m_kLoader.SaveGSpanData("tmp", m_Graphs);

    stringstream sTmp;

    sTmp << "../thirdparty/gSpan6/gSpan -f tmp -s " << dFreq << " -o -i > output.txt";

    //system ("../thirdparty/gSpan6/gSpan -f tmp -s 0.1 -o -i");
    system (sTmp.str().c_str());
    m_FrequentSGs = m_kLoader.LoadGSpanData("tmp.fp");
}

//----------------------------------------------------------------
/*
bool GraphDatabase::LoadFrequentSubgraphs(std::string filename) {
    m_FrequentSGs = m_kLoader.LoadGSpanData(filename);
}*/

//----------------------------------------------------------------
std::set< std::pair< const FrequentSubgraph*, VertexMappings > >
 GraphDatabase::GetOccuringFrequentSubgraphs(const Graph& G, unsigned int iMinSize) const
{

    typedef std::set< std::pair< const FrequentSubgraph*, std::vector< std::map<Vertex, Vertex> > > > ReturnType;
    ReturnType kRes;

    for(unsigned int i=0; i < m_FrequentSGs.size(); i++)
    {
 //       std::pair<bool, std::vector< std::map<Vertex, Vertex> > >
//GraphFunctions::IsSubgraphContained(const Graph& G1, const Graph& G2, bool bIsUnique, bool bAllMappings)
        //bool<


        std::pair<bool, std::vector< std::map<Vertex, Vertex> > > kOccuring =
        GraphFunctions::IsSubgraphContained(m_FrequentSGs[i].G, G, m_bUnique, true);

        if( kOccuring.first
                //&& num_vertices(m_pAllclusters[i]->kMeta) >= iMinC )
                && num_vertices(m_FrequentSGs[i].G) >= iMinSize )
        {

            // So this specific subgraph is contained in the graph.
            // Check: 1. If this specific subgraph is contained in any other pattern already added, don't add
            // If we pass check 1, we add it and remove all of those patterns which are contained in this specific subgraph

            // Check 1
            bool b1 = true;
            for( ReturnType::iterator it = kRes.begin(); it != kRes.end() && b1; ++it )
            {
                if( GraphFunctions::IsSubgraphContained(m_FrequentSGs[i].G, (*it).first->G, m_bUnique) )
                    b1 = false;
            }

            if( b1 )
            {
                // Add it and remove all of those patterns which are contained in this specific subgraph
                for( ReturnType::iterator it = kRes.begin(); it != kRes.end(); ++it )
                {
                    // If the pattern *it is contained in the one we're adding, remove it (since the one we're adding is bigger)
                    if( GraphFunctions::IsSubgraphContained((*it).first->G, m_FrequentSGs[i].G, m_bUnique) )
                    {
                        kRes.erase(it);
                    }
                }

                kRes.insert( make_pair(&m_FrequentSGs[i], kOccuring.second) );
            }

        }

    }

    return kRes;
}
//----------------------------------------------------------------
void GraphDatabase::RemoveDisconnectedGraphs()
{
    vector<Graph> kNewGraphs;
    BOOST_FOREACH( Graph& G, m_Graphs )
    {
        std::vector<int> component(num_vertices(G));
        int num = connected_components(G, &component[0]);


        // Now calculate the size of each component and pick the largest one as the new graph
        //------------------------------------------
        std::vector<int> componentSize(num);
        for(unsigned int i=0; i < component.size(); i++)
            componentSize[component[i]]++;
        // Now find the largest component
        int iLargestSize = -1;
        int iLargestComp = -1;
        for(unsigned int i=0; i < componentSize.size(); i++)
        {
            if( componentSize[i] > iLargestSize )
            {
                iLargestSize = componentSize[i];
                iLargestComp = i;
            }
        }
        //------------------------------------------
        // Now we simply remake the graph with only the vertices of the largest component
        // First copy the vertices into a new graph
        Graph gNew;
        list<int> vAdded;
        map<int, Vertex> vNewMap; // Map from int reference to vertex in old graph to new graph vertex
        for(unsigned int i=0; i < component.size(); i++)
        {
            // If vertex i is part of the largest component then add it to the new graph
            if( component[i] == iLargestComp )
            {
                vAdded.push_back(i);
                Vertex vNew = add_vertex(gNew);
                vNewMap[i] = vNew;

                int iId = get(vertex_name, G, i);
                put(vertex_name, gNew, vNew, iId);
            }
        }

        // Now copy all the edges that has both vertices in the new graph
        graph_traits<Graph>::edge_iterator firstE, lastE;

        for (tie(firstE, lastE) = edges(G); firstE != lastE; ++firstE)
        {
            // Make sure both source and target of this edge is in the largest component (in theory it should
            // suffice to just check one of these conditions).
            if( find(vAdded.begin(),vAdded.end(), source(*firstE,G)) != vAdded.end() &&
               find(vAdded.begin(), vAdded.end(), target(*firstE,G)) != vAdded.end() )
            {
                Vertex vSource = vNewMap[source(*firstE,G)];
                Vertex vTarget = vNewMap[target(*firstE,G)];
                add_edge(vSource, vTarget, gNew);

            }
        }


        set_property(gNew, boost::graph_name, get_property(G, graph_name));

        kNewGraphs.push_back(gNew);
        /*
        if( num == 1 )
            kNewGraphs.push_back(G);*/
    }
    cout << "Removed " << m_Graphs.size() - kNewGraphs.size() << " disconnected graphs" << endl;
    m_Graphs = kNewGraphs;
}
//----------------------------------------------------------------
void GraphDatabase::RemoveIsolatedVertices()
{
    vector<Graph> kNewGraphs;
    vector<string> sNewN;

    for(int i=0; i < m_Graphs.size(); i++)
    //BOOST_FOREACH( Graph& G, m_Graphs )
    {
        Graph G1 = m_Graphs[i];
        string sName;

        sName = get_property(m_Graphs[i], graph_name);

        GraphFunctions::RemoveIsolatedVertices(&G1);
        set_property(G1, boost::graph_name, sName);
        if( num_vertices(G1) != 0 )
        {
            kNewGraphs.push_back(G1);
            sNewN.push_back(m_kLoader.m_GraphFilenames[i]);
        }

    }
    m_kLoader.m_GraphFilenames = sNewN;
    m_Graphs = kNewGraphs;
}
//----------------------------------------------------------------
bool GraphDatabase::LoadSingleGraph(std::string sName, bool bUnique, std::string rootNodeName)
{
    pair<bool, Graph> kRes = m_kLoader.LoadSingleGraph(sName, bUnique,rootNodeName);
    if( kRes.first )
    {
        size_t found;
        m_Graphs.push_back(kRes.second);
        found=sName.find_last_of("//");
        sName = sName.substr(found+1);

        m_kLoader.m_GraphFilenames.push_back(string(sName));

    }
    return kRes.first;
}
//----------------------------------------------------------------
void GraphDatabase::GenerateCatgToCatgDist()
{

   // std::vector< std::vector< std::vector<double> > > kRes;

        std::map< std::pair<int, int>, vector<int> > kTmpRes;

        // 2. For each graph G in the graph database
        BOOST_FOREACH(Graph&G, m_Graphs)
        {
            // 3. For each vertex in the graph G
            Iter_t vi, vi_end;

            for (tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
            {
                map<int, int> kTmp;
                int iV1 = get(vertex_name, G, *vi);
                //cout << "Looking at vertex " << m_kLoader.m_IDTypes[iV1] << endl;
                int iDegree = in_degree(*vi, G);
                // For each neighbour, check what category it is
                // and add to the map
                graph_traits<Graph>::adjacency_iterator ai, ai_end;
                for (tie(ai, ai_end) = adjacent_vertices(*vi, G);
                   ai != ai_end; ++ai)
                {
                     //   cout << "Looking at neighbor " << m_kLoader.m_IDTypes[get(vertex_name, G, *ai)] << endl;
                        // Check category
                        kTmp[get(vertex_name, G, *ai)]++;
                }
                // Get the degree


                // Now divide by the degree of the vertex, and we should get for each category pair
                // a percentage
                for( map< int, int>::iterator it1 = kTmp.begin(); it1 != kTmp.end(); ++it1 )
                {
                    if( kTmpRes.find(make_pair(iV1, it1->first)) == kTmpRes.end() )
                        kTmpRes[ make_pair(iV1, it1->first) ].resize(100);

                        kTmpRes[ make_pair(iV1, it1->first) ][it1->second]++;
                }
                //if( iV1 == 1 )
                //for(int i=0; i < 10; i++)
                //    cout << "tmpRes, i: " << i << ", N: " << kTmpRes[ make_pair(iV1, 12) ][i] << endl;

            }
        }

   // m_catgDist.resize(m_kLoader.m_Types.size());

    // 1. For each category
    for( set<string>::iterator it=m_kLoader.m_Types.begin(); it != m_kLoader.m_Types.end(); ++it )
    {
        int firstcategory = GetVertexIDFromString(*it);
        std::map< int, std::vector<double> > tmpMap;

        //     m_catgDist[firstcategory] = resize(m_kLoader.m_Types.size());
        double dSum = 0.0;
        for( set<string>::iterator it2=m_kLoader.m_Types.begin(); it2 != m_kLoader.m_Types.end(); ++it2 )
        {
            double tmpSum =0.0;
            int secondcategory = GetVertexIDFromString(*it2);
            vector<int> kTmp = kTmpRes[make_pair(firstcategory,secondcategory)];
            for (unsigned int l = 0; l < kTmp.size(); l++){
                            tmpSum += kTmp[l];
                        }
            tmpMap[secondcategory].resize(100);

            for (unsigned int l = 0; l < kTmp.size(); l++){
                if(tmpSum == 0)
                    tmpMap[secondcategory][l]  = 0;
                else
                    tmpMap[secondcategory][l] = kTmp[l]; //// tmpSum;

                }


        }
        m_catgDist[firstcategory] = tmpMap;
    }
}
//----------------------------------------------------------------
void GraphDatabase::GenerateCategoryDegreeDist()
{
    //typedef std::map<std::string, std::map<unsigned int, double> > CategoryDegreeDist;
    //m_degreeDist

    cout << "Categories: " << m_kLoader.m_Types.size() << endl;

    m_degreeDist.clear();

    // 1. For each category
    for( std::set<std::string>::iterator it = m_kLoader.m_Types.begin(); it != m_kLoader.m_Types.end(); ++it )
    {
        cout << "Generating degree distribution for category " << *it << endl;
        //map< unsigned int, double > kDist;
        vector<double> vDist;
        map< unsigned int, int> kTmp;
        // 2. For each graph G in the graph database
        int j = 0;
        BOOST_FOREACH(Graph&G, m_Graphs)
        {
            // 3. For each vertex in the graph G
            Iter_t vi, vi_end;
            for (tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
            {
                // m_kLoader.m_TypesID[*it] is to convert the category type string to the int
                if( get(vertex_name, G, *vi) == m_kLoader.m_TypesID[*it] )
                {
                    // Get the degree and add one
                    kTmp[in_degree(*vi, G)]++;
                    /*
                    if( m_kLoader.m_TypesID[*it] == 1 ) // CORR
                    {
                        if( in_degree(*vi, G) == 1 )
                        {
                            cout << *it << endl;
                            cout << m_kLoader.m_GraphFilenames[j]  << endl;
                            GraphFunctions::SaveGraph("graph.dot",G, this);
                        }
                    }*/
                }
            }
            j++;
        }



        // Get the largest occuring degree for this category
        unsigned int iLargest = 0;
        double dTotal = 0.0;
        for( map< unsigned int, int>::iterator it1 = kTmp.begin(); it1 != kTmp.end(); ++it1 )
        {
            if( it1->first > iLargest )
                iLargest = it1->first;
            dTotal += (double)it1->second;
        }
        vDist.resize(iLargest+1);

        for(unsigned int i=0; i < vDist.size(); i++)
        {
            if( kTmp.find(i) != kTmp.end() )
                vDist[i] = (double)kTmp[i] / dTotal;
            else
                vDist[i] = 0.0;
        }

        m_degreeDist[ m_kLoader.m_TypesID[*it] ] = vDist;
/*
        cout << m_kLoader.m_TypesID[*it] << ", " << *it << "," << m_kLoader.m_IDTypes[m_kLoader.m_TypesID[*it]] << endl;
        double dSum = 0.0;
        for(int i = 0; i < vDist.size(); i++)
            dSum += i * vDist[i];
        cout << dSum << endl;*/
    }
}
//----------------------------------------------------------------
void GraphDatabase::ExportAveDegreesAvgCluster(std::string sFilename)
{
    ofstream out(sFilename.c_str(), ios_base::out);

    out << "Category" << '\t' << "N" << '\t' << "Avg degree" << '\t' << "Avg Cluster coeff" << endl;
    for( std::set<std::string>::iterator it = m_kLoader.m_Types.begin(); it != m_kLoader.m_Types.end(); ++it )
    {
        cout << *it << endl;
        double dSum = 0.0;
        vector<double> vDist = m_degreeDist[ m_kLoader.m_TypesID[*it] ];
        for(int i=0; i < vDist.size(); i++)
            dSum += (double)i * vDist[i];
        //dSum = dSum / (double)vDist.size();
        float fClust = GetAverageClusterCoeffForCategory(*it);
        out << *it << '\t' << m_iLastCount << '\t' << dSum << '\t' << fClust << endl;
    }

    out.close();
}
//----------------------------------------------------------------
void GraphDatabase::ExportCategoryDist(int iID, std::string sFilename)
{
    ofstream out(sFilename.c_str(), ios_base::out);

    for(unsigned int i=0; i < m_degreeDist[iID].size(); i++ )
    {
        out << i << '\t' << m_degreeDist[iID][i] << endl;
    }

    out.close();
}
//----------------------------------------------------------------
float GraphDatabase::GetAverageClusterCoeff(string sFilename) const//ExportClusterCoeffDistForCategory(string sFilename, string sCategory)
{
    float fAverage = 0.0f;

    ofstream out(sFilename.c_str(), ios_base::out);
    //BOOST_FOREACH(const Graph&G, m_Graphs)
    for(int i=0; i < m_Graphs.size(); i++)
    {
        const Graph& G = m_Graphs[i];
        // 1. Calculate the cluste coefficient map for this graph
        //std::pair<ClusteringMap, float> GraphFunctions::CalculateClusterCoeff(const Graph& G)
        std::pair<ClusteringMap, float> kRes = GraphFunctions::CalculateClusterCoeff(G);

        if( kRes.second > 0.4 && num_vertices(G) > 20 )
        {
            cout << "High!" << endl;
            cout << kRes.second << endl;
            cout << m_kLoader.m_GraphFilenames[i] << endl;
            GraphFunctions::SaveGraph("high.dot", G, this);
        }
        else if( kRes.second == 0 && num_vertices(G) > 20 )
        {
            cout << "Low!" << endl;
            cout << kRes.second << endl;
            cout << m_kLoader.m_GraphFilenames[i] << endl;
            GraphFunctions::SaveGraph("low.dot",G, this);
        }
        out << kRes.second << endl;
        fAverage += kRes.second;
    }
    out.close();
    return fAverage / (float)m_Graphs.size();
}
//----------------------------------------------------------------
float GraphDatabase::GetAverageClusterCoeffForCategory(string sCategory)
{
    int iID = GetVertexIDFromString(sCategory);

    float fAverage = 0.0;
    float fTotal = 0.0;
    BOOST_FOREACH(const Graph&G, m_Graphs)
    {
        // 1. Calculate the cluste coefficient map for this graph
        std::pair<ClusteringMap, float> kRes = GraphFunctions::CalculateClusterCoeff(G);
        Iter_t i, end;
        for(tie(i, end) = vertices(G); i != end; ++i)
        {
           // cout << setw(12) << setiosflags(ios::left)
           //         << g[*i].name << get(cm, *i) << endl;
            if( get(vertex_name, G, *i) == iID )
            {
                fTotal = fTotal + 1.0;
                fAverage += get(kRes.first, *i);
            }
        }
    }
    m_iLastCount = (int)fTotal;
    return fAverage / fTotal;
}
//----------------------------------------------------------------
void GraphDatabase::ExportClusterCoeffDistForCategory(string sFilename, string sCategory) const//ExportClusterCoeffDistForCategory(string sFilename, string sCategory)
{
    ofstream out(sFilename.c_str(), ios_base::out);
    int iID = GetVertexIDFromString(sCategory);

    BOOST_FOREACH(const Graph&G, m_Graphs)
    {
        // 1. Calculate the cluste coefficient map for this graph
        std::pair<ClusteringMap, float> kRes = GraphFunctions::CalculateClusterCoeff(G);
        Iter_t i, end;
        for(tie(i, end) = vertices(G); i != end; ++i)
        {
           // cout << setw(12) << setiosflags(ios::left)
           //         << g[*i].name << get(cm, *i) << endl;
            if( get(vertex_name, G, *i) == iID )
                out << get(kRes.first, *i) << endl;
        }
    }
    out.close();
}

//----------------------------------------------------------------
float GraphDatabase::ExportGraphStatistics(string sFilename)
{
    float kResCPL = 0.0f;
    float kCC = 0.0f;
    ofstream out(sFilename.c_str(), ios_base::out);

    set< string > sCentral;
    sCentral.insert("CORR");
    sCentral.insert("AN SV");
    sCentral.insert("LIVING");
    sCentral.insert("LOBBY");
    sCentral.insert("P CIRC");
    sCentral.insert("P WAIT");
    sCentral.insert("SECY/R");
    sCentral.insert("STKSTD");

        out << "Filename" << '\t' << "Char path len" << '\t' << "Avg Clust Coef" <<  '\t' << "Diameter" <<
 '\t' << "Num cent verts" << '\t' << "Num vertices" << endl;

    for(int i=0; i < m_Graphs.size() ; i++)
    {
        pair<float,int> kResT = GraphFunctions::GetCharacteristicPathLengthDiameter(m_Graphs[i]);
        float fCPL = kResT.first;

        std::pair<ClusteringMap, float> kRes = GraphFunctions::CalculateClusterCoeff(m_Graphs[i]);


        int iNumCentralNodes = GraphFunctions::GetNumOfVerticesOfCategory(m_Graphs[i], sCentral, *this);

       // cout << iNumCentralNodes << endl;

        kResCPL += fCPL;
        kCC += kRes.second;

        int iV = num_vertices(m_Graphs[i]);

        out << m_kLoader.m_GraphFilenames[i] << '\t' << fCPL << '\t' << kRes.second <<  '\t' << kResT.second <<
        '\t' << iNumCentralNodes << '\t' <<  iV << endl;
      //  cout << m_kLoader.m_GraphFilenames[i] << '\t' << fCPL << '\t' << kRes.second <<  '\t' << kResT.second <<
       // '\t' << iNumCentralNodes << endl;

    }

    kResCPL = kResCPL / (float)m_Graphs.size();
    kCC = kCC / (float)m_Graphs.size();

    out.close();

    return kResCPL;
}
//----------------------------------------------------------------
vector<Graph> GraphDatabase::SegmentGraph(const Graph& G, std::set<int> iCentralIDs, int iThreshold)
{

    vector<Graph> ret;


    Iter_t vi, end;
    set<Vertex> kCentral;

    // If we want to specify semantic categories as central vertices
    if( iCentralIDs.size() != 0 )
    {
        for(tie(vi, end) = vertices(G); vi != end; ++vi)
            // 1. First get a list of all the vertices that are central
            if( iCentralIDs.find(get(vertex_name, G, *vi)) != iCentralIDs.end() || in_degree(*vi, G) >= iThreshold)
                // So it is central, add it to the set of central IDs
                kCentral.insert(*vi);
    }
    else
    {
        // If the user wants the algorithm to look at the graph specifically and see which
        // vertices have a degree above a certain threshold
        //iThreshold
        for(tie(vi, end) = vertices(G); vi != end; ++vi)
            if( in_degree(*vi, G) >= iThreshold )
                // So it is central, add it to the set of central IDs
                kCentral.insert(*vi);
    }


    // A mapping from each central vertex to its corresponding set of vertices
    map<Vertex, set<Vertex> > kResMap;
    // For each central node
    for( set<Vertex>::iterator it = kCentral.begin(); it != kCentral.end(); ++it )
    {
        map<Vertex, Vertex> vMap;
        set<Vertex> kResVertexSet;
        Graph graphSegment;
        Vertex v = add_vertex(graphSegment);
        put(vertex_name, graphSegment, v, get(vertex_name, G, *it));
        vMap[*it] = v;
        // Do breadth-first search for each central node
        std::queue<Vertex> kQue;
        kQue.push(*it);
      // cout << "central node " <<  GetStringFromVertexID(get(vertex_name, G, *it)) << endl;
       set<Vertex> kExamined;

        while(kQue.size() != 0)
        {
            Vertex u = kQue.front();
            kQue.pop();

            kResVertexSet.insert(u); // Add this to the final set of vertices
            kExamined.insert(u);

            boost::graph_traits<Graph>::adjacency_iterator ai, ai_end;
            for (tie(ai, ai_end) = adjacent_vertices(u, G); ai != ai_end; ++ai)
            {
              //  cout << "neighbor" <<  GetStringFromVertexID(get(vertex_name, G, *ai)) << endl;

                // Make sure that we haven't already added this vertex
                // and that it isn't a central node
                if( kExamined.find(*ai) == kExamined.end() && kCentral.find(*ai) == kCentral.end() ){
                  //  cout << "adding " <<  GetStringFromVertexID(get(vertex_name, G, *ai)) << endl;
                    Vertex neighbor = add_vertex(graphSegment);
                    put(vertex_name, graphSegment, neighbor, get(vertex_name, G, *ai));
                     vMap[*ai] = neighbor;
                    add_edge(vMap[u], neighbor, graphSegment);
                    kQue.push(*ai);
                }
            }
        }
        kResMap[*it] = kResVertexSet;

        ret.push_back(graphSegment);
    }
    return ret;
    /*
template <typename VertexIterator>
subgraph<Graph>&
create_subgraph(VertexIterator first, VertexIterator last)
    */
}

//----------------------------------------------------------------
void GraphDatabase::RemoveGraphsBasedOnSize(int minVertices){

    vector<Graph>::iterator it=m_Graphs.begin();
    vector<string>::iterator it1 = m_kLoader.m_GraphFilenames.begin();
    cout << "Number of graphs before removal: " << m_Graphs.size() << endl;

    while(it != m_Graphs.end())
    {
        if (num_vertices(*it) < minVertices)
        {
            it = m_Graphs.erase(it);
            it1 = m_kLoader.m_GraphFilenames.erase(it1);
        }
        else
        {
            ++it;
            ++it1;
        }
    }
    cout << "Number of graphs after removal: " << m_Graphs.size() << endl;
    /*
    for (unsigned int i=0; i < m_Graphs.size(); i++)
    {
        if (num_vertices(m_Graphs[i]) < minVertices){
            m_Graphs.erase(m_Graphs.begin()+i);
            m_kLoader.m_GraphFilenames.erase(m_kLoader.m_GraphFilenames.begin()+i);
        }
    }*/
}

//----------------------------------------------------------------
void GraphDatabase::ReplaceCategories(std::map<int, int> replacementMap, Graph& G){

        BGL_FORALL_VERTICES(v, G, Graph){
            if (replacementMap.find(get(vertex_name, G,v )) != replacementMap.end()){
                put (vertex_name, G,v, replacementMap[get(vertex_name, G,v )]);
            }
        }
}
//----------------------------------------------------------------
void GraphDatabase::ReplaceCategory(std::string oldid, std::string newid){
    for (unsigned int i=0; i < m_Graphs.size(); i++){
        BGL_FORALL_VERTICES(v, m_Graphs[i], Graph){
            if (GetVertexIDFromString(oldid) == get(vertex_name,  m_Graphs[i], v )){
                put (vertex_name,  m_Graphs[i], v, GetVertexIDFromString(newid));
            }
        }
    }
}

//----------------------------------------------------------------
void  GraphDatabase::MergeCentralNodes(int iThreshold, int newVertexName){
    for (unsigned int i=0; i < m_Graphs.size(); i++){
        BGL_FORALL_VERTICES(v, m_Graphs[i], Graph){
            if (in_degree(v, m_Graphs[i]) >= iThreshold){
                put (vertex_name, m_Graphs[i],v, newVertexName);
            }
        }
    }
}
//----------------------------------------------------------------
void GraphDatabase::Blacklist(const std::set<std::string>& sBlacklist)
{
    BOOST_FOREACH( Graph& G, m_Graphs )
        G = BlacklistInternal(G, sBlacklist);
}
//----------------------------------------------------------------
Graph GraphDatabase::BlacklistInternal
            (const Graph& G, const set<string>& sBlacklist)
{
    // We shall constuct a temporary new graph and then
    // overwrite the old
    Graph gTmp;



    Iter_t vi, vi_end, next;

    // Maintain a mapping from the old vertex descriptor -> new descriptor
    map< Vertex, Vertex*> tmpMapping;

    bool bBlacklisted = false;
    for (tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
    {
        bBlacklisted = false;
        tmpMapping[*vi] = 0;

        //bBlacklisted =
        //    (find(sBlacklist.begin(), sBlacklist.end(), G[*vi].sName) != sBlacklist.end());
        BOOST_FOREACH( const string& s, sBlacklist )
        {

            if( m_kLoader.m_IDTypes[get(vertex_name, G, *vi)].compare(s) == 0 )
                bBlacklisted = true;
        }

        if( !bBlacklisted )
        {
            Vertex* ver = new Vertex(add_vertex(gTmp));
            //gTmp[*ver] = G[*vi];
            int iID = get(vertex_name, G, *vi);//m_TypesID.find(G[*vi].sName)->second;

            put(vertex_name, gTmp, *ver, iID);

            tmpMapping[*vi] = ver;
        }
    }


    graph_traits<Graph>::edge_iterator firstE, lastE;
    // Go through all the edges of the old graph and only add those which have verticies
    // which are existing in the transformed graph.

    // Also, for all those edges (u,v) where u or v is one of the blacklisted vertices
    // make it so that its edges
    for (tie(firstE, lastE) = edges(G); firstE != lastE; ++firstE)
    {
            if( tmpMapping[source(*firstE, G)] != 0 && tmpMapping[target(*firstE, G)] != 0  )
            {

                pair<Edge, bool> kRet2 = edge(*tmpMapping[source(*firstE, G)], *tmpMapping[target(*firstE, G)], gTmp);

                if( !kRet2.second )
                    std::pair<Edge, bool> kRet =
                    add_edge(*tmpMapping[source(*firstE, G)], *tmpMapping[target(*firstE, G)], gTmp);
            }
            else
            {
                // Either u or v is blacklisted, (or both).
                // If both are blacklisted, we want to connect all the valid adjacent vertices
                // to each other

                // Assume only one is blacklisted
                Vertex vBlackList;
                Vertex vOther;
                if( tmpMapping[source(*firstE, G)] == 0 )
                {
                    vBlackList = source(*firstE, G);
                    vOther = target(*firstE, G);
                }
                else
                {
                    vBlackList = target(*firstE, G);
                    vOther = source(*firstE, G);
                }

                if( tmpMapping[vOther] != 0 )
                {
                // Go through all the blacklisted ones adjacent vertices
                // We want to connect these to the vOther vertex (if they are not already connected)
                graph_traits<Graph>::adjacency_iterator v1, v2;
                bool bFound = false;
                for( tie(v1, v2) = adjacent_vertices(vBlackList, G); (v1 != v2); ++v1 )
                {
                    // Check if this vertex *v1 is already connected to VOther
                    // If not, add the connection
                    pair<Edge, bool> kRet = edge( *v1, vOther, G);
/*
                    cout << *vi << ", " << vOther << endl;
                    cout << tmpMapping[*v1] << endl;
                    cout << tmpMapping[vOther] << endl;*/
                    // Add if it doesn't exist
                    if( !kRet.second && *v1 != vOther && tmpMapping.find(*v1) != tmpMapping.end() && tmpMapping[*v1] != 0 )
                        kRet = add_edge(*tmpMapping[*v1], *tmpMapping[vOther], gTmp);
                }
                }
            }
    }

    //Graph kFinalGraph;

    for(map<Vertex, Vertex*>::const_iterator i = tmpMapping.begin(); i != tmpMapping.end(); ++i)
        delete i->second;

    tmpMapping.clear();

    // 3. We must also remove those vertices which have no more edges
    //---------------------------------------------
    GraphFunctions::RemoveIsolatedVertices(&gTmp);
    //---------------------------------------------
    // End of step 3

    // Copy the graph name as well
    set_property(gTmp, boost::graph_name, get_property(G,boost::graph_name));

    return gTmp;
}

void GraphDatabase::BlacklistOnCriterion(int iThreshold)
{
    set<string> kBlacklist = InternalGenerateBlacklist(iThreshold);

    cout << "Starting blacklist..." << endl;
    for( set<string>::iterator it = kBlacklist.begin(); it != kBlacklist.end(); ++it )
    {
        set<string> tmpSet;
        tmpSet.insert(*it);
        cout << "Blacklisting: " << *it << endl;
        Blacklist(tmpSet);
        //if( m_kLoader.m_Types.find(*it) != m_kLoader.m_Types.end() )
        //    m_kLoader.m_Types.erase(m_kLoader.m_Types.find(*it));
    }

    set<string> kNew;
    for( set<string>::iterator it = m_kLoader.m_Types.begin(); it != m_kLoader.m_Types.end(); ++it )
    {
        bool bAdd = true;
        for( set<string>::iterator it1 = kBlacklist.begin(); it1 != kBlacklist.end(); ++it1 )
        {
            if( (*it1).compare(*it) == 0 )
            {
                bAdd = false;
                break;
            }
        }
        if( bAdd )
            kNew.insert(*it);
    }
    m_kLoader.m_Types = kNew;

    cout << "Blacklisted " << kBlacklist.size() << " vertices. Remaining: " << m_kLoader.m_Types.size() << endl;
}

set<string> GraphDatabase::InternalGenerateBlacklist(int iThreshold)
{
    set<string> kBlacklist;

    // Get a map from string -> int
    map< string, int > kMapCounter;

    for( set<string>::iterator it = m_kLoader.m_Types.begin(); it != m_kLoader.m_Types.end(); ++it )
        kMapCounter[*it] = 0;

    // For each graph
    for(int i=0; i < m_Graphs.size(); i++)
    {
            Iter_t vi, vi_end;

            for (tie(vi, vi_end) = vertices(m_Graphs[i]); vi != vi_end; ++vi)
            {
                int iID = get(vertex_name, m_Graphs[i], *vi);
                kMapCounter[ m_kLoader.m_IDTypes[iID] ]++;
            }
    }

    for( map< string, int >::iterator it = kMapCounter.begin(); it != kMapCounter.end(); ++it )
        if( it->second < iThreshold )
            kBlacklist.insert(it->first);



    return kBlacklist;
}

//----------------------------------------------------------------
void GraphDatabase::ExportGraphsToDot(std::string path){

     for (unsigned int i=0; i < m_Graphs.size(); i++){
         cout << "Writing graph " << i << " of " << m_Graphs.size() << endl;
         GraphFunctions::SaveGraphToFile(path +  m_kLoader.m_GraphFilenames[i] + ".dot",m_Graphs[i], *this);
    }
}
//----------------------------------------------------------------
int GraphDatabase::GetGraphNameFromID(std::string sName)
{
    for(int i=0; i < m_kLoader.m_GraphFilenames.size(); i++)
    {
        if( sName.compare(m_kLoader.m_GraphFilenames[i]) == 0 )
            return i;
    }
    return -1;
}
//----------------------------------------------------------------
